package cn.orange.ch03_linked;

import cn.orange.ListNode;

/**
 * LC24.两两交换链表中的节点
 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）
 */
public class LC24 {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        /*
        //方法1
        ListNode newHead = head.next;
        ListNode nxt = swapPairs(head.next.next);
        newHead.next = head;
        head.next = nxt;
        return newHead;
        */
        //方法2
        ListNode nxt = head.next.next;
        ListNode newHead = head.next;
        newHead.next = head;
        head.next = swapPairs(nxt);
        return newHead;
    }
    public static void main(String[] args) {
        LC24 alg = new LC24();
        ListNode h1 = new ListNode(1, new ListNode(2, new ListNode(6, new ListNode(4, new ListNode(5, new ListNode(6))))));
        System.out.println(alg.swapPairs(h1));
        ListNode h2 = new ListNode(1, new ListNode(2, new ListNode(3)));
        System.out.println(alg.swapPairs(h2));
    }
}
